package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.TreeNode;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ValidateBinarySearchTree {

    /**
     *
     * 平衡二叉树的值满足：
     * 1. 节点的左子树只包含小于当前节点的数。
     * 2. 节点的右子树只包含大于当前节点的数。
     * 3. 所有左子树和右子树自身必须也是二叉搜索树。
     * 因此每个节点的值都在一个区间中，
     * 比如：
     *       5
     *     /   \
     *   4      8
     *         / \
     *        7   9
     * 节点 4 就在 (-∞, 5) 之间 ，节点 7 在 (5,8)之间
     */
    public boolean isValidBST(TreeNode root) {
        return preorderValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean preorderValid(TreeNode root, long left, long right){
        if (root == null){
            return true;
        }
        if (root.val <= left || root.val >= right){
            return false;
        }
        return preorderValid(root.left, left, root.val) && preorderValid(root.right, root.val, right);
    }

    /**
     * 中序遍历树，得到的结果为按升序遍历
     */
    private boolean inorderTravel(TreeNode root){
        LinkedList<TreeNode> stack = new LinkedList<>();
        long pre = Long.MIN_VALUE;
        while (!stack.isEmpty() || root != null){
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.val <= pre){
                return false;
            }
            pre = root.val;
            root = root.right;
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree(5,4,7,null,null,6,8);
        PrintUtils.println(root);
        PrintUtils.println("===============");
        boolean res = new ValidateBinarySearchTree().isValidBST(root);
        boolean res1 = new ValidateBinarySearchTree().inorderTravel(root);
        System.out.println(res);
        System.out.println(res1);
    }

}
